<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  

  
  <title>顾伊凡</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta property="og:type" content="website">
<meta property="og:title" content="顾伊凡">
<meta property="og:url" content="http://yoursite.com/index.html">
<meta property="og:site_name" content="顾伊凡">
<meta property="og:locale" content="default">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="顾伊凡">
  
    <link rel="alternate" href="/atom.xml" title="顾伊凡" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  <link rel="stylesheet" href="/css/style.css">
</head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">顾伊凡</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main">
  
    <article id="post-写了一个可以拦截ajax请求并修改返回结果的插件" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2019/03/04/写了一个可以拦截ajax请求并修改返回结果的插件/" class="article-date">
  <time datetime="2019-03-04T08:06:05.000Z" itemprop="datePublished">2019-03-04</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2019/03/04/写了一个可以拦截ajax请求并修改返回结果的插件/">写了一个可以拦截ajax请求并修改返回结果的chrome插件</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>这个插件可以拦截页面上的 ajax 请求，并把返回结果替换成任意文本。它对 mock 数据、排查一些线上问题等会有很大帮助。（当然 chales 等抓包软件也可以做到，然而使用起来比较繁琐，做成 chrome 插件的形式会方便许多）</p>
<p>以下是使用效果，通过修改 ajax 请求结果，我把第一条文章标题替换成了“这标题特调皮（Σ（ﾟдﾟlll）句内三押×2）”：</p>
<img src="/2019/03/04/写了一个可以拦截ajax请求并修改返回结果的插件/拦截掘金.png" width="600">
<h1 id="使用示例（视频）"><a href="#使用示例（视频）" class="headerlink" title="使用示例（视频）"></a>使用示例（视频）</h1><p><a href="http://t.cn/EMvR6pa?m=4347641385182648&amp;u=5352731024" target="_blank" rel="noopener">http://t.cn/EMvR6pa?m=4347641385182648&amp;u=5352731024</a></p>
<h1 id="Chrome-商店地址"><a href="#Chrome-商店地址" class="headerlink" title="Chrome 商店地址"></a>Chrome 商店地址</h1><p>地址：<a href="https://chrome.google.com/webstore/detail/ajax-interceptor/nhpjggchkhnlbgdfcbgpdpkifemomkpg" target="_blank" rel="noopener">https://chrome.google.com/webstore/detail/ajax-interceptor/nhpjggchkhnlbgdfcbgpdpkifemomkpg</a></p>
<p>你也可以直接搜索 <b>Ajax Interceptor</b> 进行安装</p>
<h1 id="注意"><a href="#注意" class="headerlink" title="注意"></a>注意</h1><ol>
<li>当你不需要使用该插件时，建议把开关关上，以免对页面正常浏览造成影响</li>
<li>暂不支持由 fetch 发起的请求</li>
</ol>
<h1 id="大致原理"><a href="#大致原理" class="headerlink" title="大致原理"></a>大致原理</h1><p>页面加载时往页面上注入 js 代码，这段 js 会生成一个 XMLHttpRequest 的代理对象，并把 window.XMLHttpRequest 替换成这个对象。该对象又会对 onreadystatechange 和 onload 两个回调函数做特殊处理，把 responseText 和 response 的值覆盖为你设置的值。更详细的原理推荐看下这篇文章：<a href="https://www.jianshu.com/p/7337ac624b8e" target="_blank" rel="noopener">https://www.jianshu.com/p/7337ac624b8e</a> ，该插件实现原理与之基本类似。<br>其它就是这段页面上的 js 代码和右侧弹出的 iframe (用户界面)以及插件后台代码一些数据交互和存储上的实现，这部分比较杂就不介绍了~</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2019/03/04/写了一个可以拦截ajax请求并修改返回结果的插件/" data-id="cjt066zfj0001e0z4ow7k8twn" class="article-share-link">Share</a>
      
      
    </footer>
  </div>
  
</article>


  
    <article id="post-Javascript的尾递归及其优化" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2018/10/17/Javascript的尾递归及其优化/" class="article-date">
  <time datetime="2018-10-17T06:01:47.000Z" itemprop="datePublished">2018-10-17</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2018/10/17/Javascript的尾递归及其优化/">Javascript的尾递归及其优化</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>在平时的代码里，递归是很常见的，然而它可能会带来的调用栈溢出问题有时也令人头疼：<br><img src="/2018/10/17/Javascript的尾递归及其优化/overflow.png" width="600"><br>我们知道， js 引擎（包括大部分语言）对于函数调用栈的大小是有限制的，如下图（虽然都是很老的浏览器，但还是有参考价值）：<br><img src="/2018/10/17/Javascript的尾递归及其优化/browsers-overflow.png" width="600"><br>为了解决递归时调用栈溢出的问题，除了把递归函数改为迭代的形式外，改为<code>尾递归</code>的形式也可以解决（虽然目前大部分浏览器没有对尾递归（尾调用）做优化，依然会导致栈溢出，但了解尾递归的优化方式还是有价值的。而且我们可以通过一个统一的工具函数把尾递归转化为不会溢出的形式，这些下文会一一展开）。<br>在讨论<code>尾递归</code>之前，我们先了解一下<code>尾调用</code>，以及 js 引擎如何对其进行优化。</p>
<h1 id="尾调用"><a href="#尾调用" class="headerlink" title="尾调用"></a>尾调用</h1><p>当函数<code>a</code>的最后一个动作是调用函数<code>b</code>时，那么对函数<code>b</code>的调用形式就是<code>尾调用</code>。比如下面的代码里对<code>fn1</code>的调用就是尾调用：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> fn1 = <span class="function">(<span class="params">a</span>) =&gt;</span> &#123;</span><br><span class="line">  <span class="keyword">let</span> b = a + <span class="number">1</span>;</span><br><span class="line">  <span class="keyword">return</span> b;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> fn2 = <span class="function">(<span class="params">x</span>) =&gt;</span> &#123;</span><br><span class="line">  <span class="keyword">let</span> y = x + <span class="number">1</span>;</span><br><span class="line">  <span class="keyword">return</span> fn1(y);        <span class="comment">// line A</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> result = fn2(<span class="number">1</span>);  <span class="comment">// line B</span></span><br></pre></td></tr></table></figure><br>我们知道，在代码执行时，会产生一个调用栈，调用某个函数时会将其压入栈，当它 return 后就会出栈，下图是对于这段代码简易示例的调用栈（没有对<code>尾调用</code>做优化）：<br><img src="/2018/10/17/Javascript的尾递归及其优化/callWithoutOpt.png" width="600"><br>首先<code>fn2</code>被压入栈，<code>x</code>、<code>y</code>依次被创建并赋值，栈内也会记录相应的信息，同时也记录了该函数被调用的地方，这样在函数 return 后就能知道结果应该返回到哪里。然后<code>fn1</code>入栈，当它运行结束后就可以出栈，之后<code>fn2</code>也得到了想要的结果，返回结果后也出栈，此段代码运行结束。<br>仔细看一下以上过程，你有没有觉得第二第三步中<code>fn2</code>的存在有些多余？它内部的一切计算都已经完成了，此时它在栈内的唯一作用就是记录最后结果应该返回到哪一行。因而可以有如下的优化：<br><img src="/2018/10/17/Javascript的尾递归及其优化/callWithOpt.png" width="600"><br>在第二步调用<code>fn1</code>时，<code>fn2</code>即可出栈，并把<code>line B</code>信息给<code>fn1</code>，然后将<code>fn1</code>入栈，最后把<code>fn1</code>的结果返回到<code>line B</code>即可，这样就减小了调用栈的大小。</p>
<h1 id="辨别是否是尾调用"><a href="#辨别是否是尾调用" class="headerlink" title="辨别是否是尾调用"></a>辨别是否是尾调用</h1><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> a = <span class="function"><span class="params">()</span> =&gt;</span> &#123;</span><br><span class="line">  b();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这里<code>b</code>的调用不是尾调用，因为函数<code>a</code>在调用<code>b</code>后还隐式地执行了一段<code>return undefined</code>，如下面这段代码：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> a = <span class="function"><span class="params">()</span> =&gt;</span> &#123;</span><br><span class="line">  b();</span><br><span class="line">  <span class="keyword">return</span> <span class="literal">undefined</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><br>如果我们把它当做<code>尾调用</code>并按照上面的方法优化的话，就得不到函数<code>a</code>正确的返回结果了。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> a = <span class="function"><span class="params">()</span> =&gt;</span> b() || c();</span><br><span class="line"><span class="keyword">const</span> a1 = <span class="function"><span class="params">()</span> =&gt;</span> b() &amp;&amp; c();</span><br></pre></td></tr></table></figure>
<p>这里<code>a</code>和<code>a1</code>中的<code>b</code>都不是<code>尾调用</code>，因为在它调用之后还有判断的动作以及可能的对于<code>c</code>的调用，而<code>c</code>都是<code>尾调用</code>。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> a = <span class="function"><span class="params">()</span> =&gt;</span> &#123;</span><br><span class="line">  <span class="keyword">let</span> result = b();</span><br><span class="line">  <span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>对于这段代码，有文章指出<code>b</code>并不是<code>尾调用</code>，即便它与<code>const a = () =&gt; b()</code>是等价的，而后者显然是尾调用。这就涉及到定义的问题了，我觉得不必过于纠结，<code>尾调用</code>的真正目的是为了进行优化，防止栈溢出，我测试了下支持<code>尾调用</code>的 safari 浏览器，在严格模式下用类似的代码执行一段递归函数，结果是不会导致栈溢出，所以 safari 对这种形式的代码做了优化。</p>
<h1 id="尾递归"><a href="#尾递归" class="headerlink" title="尾递归"></a>尾递归</h1><p>现在就轮到本篇文章的主角——<code>尾递归</code>了，看一下下面这段简单的递归代码：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> sum = <span class="function">(<span class="params">n</span>) =&gt;</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (n &lt;= <span class="number">1</span>) <span class="keyword">return</span> n;</span><br><span class="line">  <span class="keyword">return</span> n + sum(n<span class="number">-1</span>)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><br>就是计算从1到n的整数的和，显然这段代码并不是<code>尾递归</code>，因为<code>sum(n-1)</code>调用后还需要一步计算的过程，所以当n较大时就会导致栈溢出。我们可以把这段代码改为<code>尾递归</code>的形式：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> sum = <span class="function">(<span class="params">n, prevSum = <span class="number">0</span></span>) =&gt;</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (n &lt;= <span class="number">1</span>) <span class="keyword">return</span> n + prevSum;</span><br><span class="line">  <span class="keyword">return</span> sum(n<span class="number">-1</span>, n + prevSum)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><br>这样就是<code>尾递归</code>了，这段代码在 safari 里以严格模式运行时，不会出现栈溢出错误，因为它对<code>尾调用</code>做了优化。那有多少浏览器会做优化呢？其实在<a href="http://www.ecma-international.org/ecma-262/6.0/#sec-tail-position-calls" target="_blank" rel="noopener"> es6 的规范里</a>，就已经定义了对<code>尾调用</code>的优化，不过目前浏览器对其支持情况很不好:<br><img src="/2018/10/17/Javascript的尾递归及其优化/browserSupport.png" title="100%"><br>具体见<a href="http://kangax.github.io/compat-table/es6/#test-proper_tail_calls_%28tail_call_optimisation%29" target="_blank" rel="noopener">这里</a><br>即便将来大部分浏览器都支持<code>尾调用</code>优化了，按照 es6 的规范，也只会在严格模式下触发，这明显会很不方便。那我们把递归函数转为<code>尾递归</code>有什么用呢？其实我们可以通过一个统一的方法对<code>尾递归</code>函数进行处理，让其不再导致栈溢出。</p>
<h1 id="Trampoline"><a href="#Trampoline" class="headerlink" title="Trampoline"></a>Trampoline</h1><p><a href="https://en.wikipedia.org/wiki/Tail_call#Through_trampolining" target="_blank" rel="noopener">Trampoline</a>是对<code>尾递归</code>函数进行处理的一种技巧。我们需要先把上面的<code>sum</code>函数改造一下，再由<code>trampoline</code>函数处理即可：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> sum0 = <span class="function">(<span class="params">n, prevSum = <span class="number">0</span></span>) =&gt;</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (n &lt;= <span class="number">1</span>) <span class="keyword">return</span> n + prevSum;</span><br><span class="line">  <span class="keyword">return</span> <span class="function"><span class="params">()</span> =&gt;</span> sum0(n<span class="number">-1</span>, n + prevSum)</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">const</span> trampoline = <span class="function"><span class="params">f</span> =&gt;</span> (...args) =&gt; &#123;</span><br><span class="line">  <span class="keyword">let</span> result = f(...args);</span><br><span class="line">  <span class="keyword">while</span> (<span class="keyword">typeof</span> result === <span class="string">'function'</span>) &#123;</span><br><span class="line">    result = result();</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">const</span> sum = trampoline(sum0);</span><br><span class="line"></span><br><span class="line"><span class="built_in">console</span>.log(sum(<span class="number">1000000</span>)); <span class="comment">// 不会栈溢出</span></span><br></pre></td></tr></table></figure><br>可以看到，这里实际上就是把原本的递归改为了迭代，这样就不会有栈溢出的问题啦。</p>
<p>当然，如果一个方法可以写成<code>尾递归</code>的形式，那它肯定也能被写成迭代的形式，但有些场景下使用递归可能会更加直观，如果它能被转为<code>尾递归</code>，你就可以直接用<code>trampoline</code>函数进行处理，或者把它改写成迭代的方法（或者等大部分浏览器支持<code>尾递归</code>优化后在严格模式下执行）</p>
<blockquote>
<h3 id="参考："><a href="#参考：" class="headerlink" title="参考："></a>参考：</h3><p><a href="https://blog.logrocket.com/using-trampolines-to-manage-large-recursive-loops-in-javascript-d8c9db095ae3" target="_blank" rel="noopener">https://blog.logrocket.com/using-trampolines-to-manage-large-recursive-loops-in-javascript-d8c9db095ae3</a><br><a href="http://2ality.com/2015/06/tail-call-optimization.html" target="_blank" rel="noopener">http://2ality.com/2015/06/tail-call-optimization.html</a><br><a href="https://www.zhihu.com/question/30078697/answer/146047599" target="_blank" rel="noopener">https://www.zhihu.com/question/30078697/answer/146047599</a></p>
</blockquote>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2018/10/17/Javascript的尾递归及其优化/" data-id="cjt066zfe0000e0z4wmtot6vi" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/尾递归-尾调用-trampoline-递归-迭代/">尾递归,尾调用,trampoline,递归,迭代</a></li></ul>

    </footer>
  </div>
  
</article>


  
    <article id="post-深入探究immutable.js的实现机制（二）" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2018/09/19/深入探究immutable.js的实现机制（二）/" class="article-date">
  <time datetime="2018-09-19T08:55:46.000Z" itemprop="datePublished">2018-09-19</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2018/09/19/深入探究immutable.js的实现机制（二）/">深入探究immutable.js的实现机制（二）</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>上一篇我们研究了 Immutable.js 持久化数据结构的基本实现原理，对其核心数据结构<code>Vector Trie</code>进行了介绍，并着重探究了其中的<code>位分区</code>机制。采用<code>位分区</code>的根本原因是为了优化速度，而对于空间的优化， Immutable.js 是怎么做的呢？接下来先探讨下这点。</p>
<h1 id="HAMT"><a href="#HAMT" class="headerlink" title="HAMT"></a>HAMT</h1><p><code><a href="https://en.wikipedia.org/wiki/Hash_array_mapped_trie" target="_blank" rel="noopener">HAMT</a></code>全称<code>hash array mapped trie</code>，其基本原理与上篇所说的<code>Vector Trie</code>非常相似，不过它会对树进行压缩，以节约一些空间。 Immutable.js 参考了<code>HAMT</code>对树进行了高度和节点内部的压缩。</p>
<h1 id="树高压缩"><a href="#树高压缩" class="headerlink" title="树高压缩"></a>树高压缩</h1><p>假设我们有一个 2 叉 <code>Vector Trie</code>，现在存了一个值，key为<code>110</code>，它会被存到<code>0</code> <code>1</code> <code>1</code>这条路径下，如下图：<br><img src="/2018/09/19/深入探究immutable.js的实现机制（二）/trie1.png" width="350"><br>显然，这图里展示的结构已经进行了最简单的优化，因为现在只存了一个值，所以把与<code>110</code>无关的节点去掉了。还能进行什么优化吗？我们发现，中间那两个节点也是可以去掉的，如下图：<br><img src="/2018/09/19/深入探究immutable.js的实现机制（二）/trie2.png" width="310"><br>获取该值时，我们先从<code>0</code>找下来，发现这直接是一个根节点，那取它存储的值就行了。就是说在不产生混淆的情况下，我们可以用尽可能少的二进制位去标识这个 key 。这样我们就进行了高度上的压缩，既减少了空间，又减少了查找和修改的时间。<br>如果要添加一个值，它的 key 结尾也是<code>0</code>，该怎么做呢？很简单，如下图：<br><img src="/2018/09/19/深入探究immutable.js的实现机制（二）/trie3.png" width="340"><br>我们只要在需要的时候增加或减少节点即可。</p>
<h1 id="节点内部压缩-Bitmap"><a href="#节点内部压缩-Bitmap" class="headerlink" title="节点内部压缩-Bitmap"></a>节点内部压缩-Bitmap</h1><p>上一篇我们提到， Immutable.js 的 Trie 里，每个节点数组的长度是 32 ，然而在很多情况下，这 32 个位置大部分是用不到的，这么大的数组显然也占用了很大空间。使用<code>Bitmap</code>，我们就可以对数组进行压缩。<br>我们先拿长度为 8 的数组举例：<br><img src="/2018/09/19/深入探究immutable.js的实现机制（二）/bitmap1.png" width="300"><br>我们实际上只是用了数组的下标对 key 进行索引，这样想数组第 5、6、7 位显然目前是毫无作用的，那 0、2、3 呢？我们有必要为了一个下标 4 去维持一个长度为5的数组吗？我们只需要指明“假想数组”中下标为 1 和为 4 的位置有数就可以了。这里就可以用到<code><a href="https://en.wikipedia.org/wiki/Bit_array" target="_blank" rel="noopener">bitmap</a></code>，如下：<br><img src="/2018/09/19/深入探究immutable.js的实现机制（二）/bitmap2.png" width="300"><br>我们采用了一个数，以其二进制形式表达“假想的长度为8的数组”中的占位情况，1 表示数组里相应下标位置有值，0 则表示相应位置为空。比如这个二进制数第 4 位（从右往左，从 0 开始数）现在是 1 ，就表示数组下标为 4 的位置有值。这样原本的长度为 8 的数组就可以压缩到 2 。<br>注意这个数组中的元素还是按照“假想数组”中的顺序排列的，这样我们若要取“假想数组”中下标为 i 的元素时，首先是判断该位置有没有值，若有，下一步就是得到在它之前有几个元素，即在二进制数里第 i 位之前有多少位为 1 ，假设数量为 a ，那么该元素在当前压缩后的数组里下标就是 a 。<br>具体操作中，我们可以通过<code>bitmap &amp; (1 &lt;&lt; i - 1)</code>，得到一个二进制数，该二进制数中只有第 i 位之前有值的地方为 1 ，其余全为 0 ，下面我们只需统计该二进制数里 1 的数量即可得到下标。计算二进制数中 1 数量的过程被称作<code><a href="https://en.wikipedia.org/wiki/Hamming_weight" target="_blank" rel="noopener">popcount</a></code>，具体算法有很多，我了解不多就不展开了，前面点击后是维基的地址，感兴趣的可以研究下。<br>下面我们看一下这部分的源码：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">get(shift, keyHash, key, notSetValue) &#123;</span><br><span class="line">  <span class="keyword">if</span> (keyHash === <span class="literal">undefined</span>) &#123;</span><br><span class="line">    keyHash = hash(key);</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">const</span> bit = <span class="number">1</span> &lt;&lt; ((shift === <span class="number">0</span> ? keyHash : keyHash &gt;&gt;&gt; shift) &amp; MASK);</span><br><span class="line">  <span class="keyword">const</span> bitmap = <span class="keyword">this</span>.bitmap;</span><br><span class="line">  <span class="keyword">return</span> (bitmap &amp; bit) === <span class="number">0</span></span><br><span class="line">    ? notSetValue</span><br><span class="line">    : <span class="keyword">this</span>.nodes[popCount(bitmap &amp; (bit - <span class="number">1</span>))].get(</span><br><span class="line">        shift + SHIFT,</span><br><span class="line">        keyHash,</span><br><span class="line">        key,</span><br><span class="line">        notSetValue</span><br><span class="line">      );</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><br>可见它与我们上一篇看到的源码并没有太大不同（Immutable.js 里如果一个数组占用不超过一半（ 16 个），就会对其进行压缩，上一篇的源码就是没有压缩下的情况），就是多了一个用 bitmap 计算数组下标的过程，方式也跟上文所讲的一样，对于这个<code>popCount</code>方法，我把源码也贴出来：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">popCount</span>(<span class="params">x</span>) </span>&#123;</span><br><span class="line">  x -= (x &gt;&gt; <span class="number">1</span>) &amp; <span class="number">0x55555555</span>;</span><br><span class="line">  x = (x &amp; <span class="number">0x33333333</span>) + ((x &gt;&gt; <span class="number">2</span>) &amp; <span class="number">0x33333333</span>);</span><br><span class="line">  x = (x + (x &gt;&gt; <span class="number">4</span>)) &amp; <span class="number">0x0f0f0f0f</span>;</span><br><span class="line">  x += x &gt;&gt; <span class="number">8</span>;</span><br><span class="line">  x += x &gt;&gt; <span class="number">16</span>;</span><br><span class="line">  <span class="keyword">return</span> x &amp; <span class="number">0x7f</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h1 id="为什么是32"><a href="#为什么是32" class="headerlink" title="为什么是32"></a>为什么是32</h1><p>上一篇我们提到了 Immutable.js 的 Vector Trie 采用了 32 作为数组的长度，也解释了由于采用了<code>位分区</code>，该数字只能是2的整数次幂，所以不能是 31、33 等。但8、16、64等等呢？这是通过实际测试得出的，见下图：<br><img src="/2018/09/19/深入探究immutable.js的实现机制（二）/time.png" width="500"><br>图中分别是查找和更新的时间，看上去似乎 8 或 16 更好？考虑到平时的使用中，查找比更新频次高很多，所以 Immutable.js 选择了 32。</p>
<h1 id="回顾"><a href="#回顾" class="headerlink" title="回顾"></a>回顾</h1><p>现在，我们就能理解第一篇文章开头的截图了：<br><img src="/2018/09/19/深入探究immutable.js的实现机制（二）/console截图.png" width="500"><br><img src="/2018/09/19/深入探究immutable.js的实现机制（二）/console截图2.png" width="500"><br>我们可以看到， map 里主要有三种类型的节点：</p>
<ul>
<li><code>HashArrayMapNode</code>，拥有的子节点数量 ＞16 ，拥有的数组长度为 32</li>
<li><code>BitmapIndexedNode</code>，拥有的子节点数量 ≤16 ，拥有的数组长度与子节点数量一致，经由 bitmap 压缩</li>
<li><code>ValueNode</code>，叶子节点，存储 key 和 value</li>
</ul>
<p>此外，每个节点似乎都有个<code>ownerID</code>属性，这又是做什么的呢？它涉及到 Immutable.js 中的可变数据结构。</p>
<h1 id="Transient"><a href="#Transient" class="headerlink" title="Transient"></a>Transient</h1><p>其实可以说 Immutable.js 中的数据结构有两种形态，“不可变”和“可变”。虽然“不可变”是 Immutable.js 的主要优势，但“可变”形态下的操作当然效率更高。有时对于某一系列操作，我们只需要得到这组操作结束后的状态，若中间的每一个操作都用不可变数据结构去实现显然有些多余。这种情景下，我们就可以使用<code><a href="http://facebook.github.io/immutable-js#batching-mutations" target="_blank" rel="noopener">withMutations</a></code>方法对相应数据结构进行临时的“可变”操作，最后再返回一个不可变的结构，这就是<code>Transient</code>，比如这样：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> map = <span class="keyword">new</span> Immutable.Map(&#123;&#125;);</span><br><span class="line">map = map.withMutations(<span class="function">(<span class="params">m</span>) =&gt;</span> &#123;</span><br><span class="line">  <span class="comment">// 开启Transient</span></span><br><span class="line">  m.set(<span class="string">'a'</span>, <span class="number">1</span>); <span class="comment">// 我们可以直接在m上进行修改，不需要 m = m.set('a', 1)</span></span><br><span class="line">  m.set(<span class="string">'b'</span>, <span class="number">2</span>);</span><br><span class="line">  m.set(<span class="string">'c'</span>, <span class="number">3</span>);</span><br><span class="line">&#125;);</span><br><span class="line"><span class="comment">// Transient结束</span></span><br></pre></td></tr></table></figure><br>实际上， Immutable.js 里很多方法都使用了<code>withMutations</code>构造临时的可变数据结构来提高效率，比如 Map 中的<code>map</code>、<code>deleteAll</code>方法以及 Map 的构造函数。而在一个不可变数据结构中实现临时的可变数据结构的关键（有点拗口XD），就是这个<code>ownerID</code>。下图对比了使用与不使用<code>Transient</code>时的区别：<br><img src="/2018/09/19/深入探究immutable.js的实现机制（二）/transient.png" width="600"><br>显然，使用<code>Transient</code>后由于无需每次生成新的节点，效率会提高空间占用会减少。在开启<code>Transient</code>时，根节点会被赋与一个新的<code>ownerID</code>，在<code>Transient</code>完成前的每一步操作只需遵循下面的逻辑即可：</p>
<ol>
<li>若要操作的节点的<code>ownerID</code>与父节点的不一致，则生成新的节点，把旧节点上的值拷贝过来，其<code>ownerID</code>更新为父节点的<code>ownerID</code>，然后进行相应操作；</li>
<li>若要操作的节点的<code>ownerID</code>与父节点的一致，则直接在该节点上操作；<br>下面先我们看下 Immutable.js 中开启<code>Transient</code>的相关源码：<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">OwnerID</span>(<span class="params"></span>) </span>&#123;&#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">asMutable</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> <span class="keyword">this</span>.__ownerID ? <span class="keyword">this</span> : <span class="keyword">this</span>.__ensureOwner(<span class="keyword">new</span> OwnerID());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">withMutations</span>(<span class="params">fn</span>) </span>&#123;</span><br><span class="line">  <span class="keyword">const</span> mutable = <span class="keyword">this</span>.asMutable();</span><br><span class="line">  fn(mutable);</span><br><span class="line">  <span class="keyword">return</span> mutable.wasAltered() ? mutable.__ensureOwner(<span class="keyword">this</span>.__ownerID) : <span class="keyword">this</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
它给了根节点一个<code>ownerID</code>，这个<code>ownerID</code>会在接下来的操作中按照上面的逻辑使用。这段代码有个“骚操作”，就是用 JS 的对象地址去作为 ID ，因为每次 new 之后的对象的地址肯定与之前的对象不同，所以用这种方法可以很简便高效地构造一套 ID 体系。<br>下面再看下开启后进行操作时的一段源码（ Map 中的<code>set</code>操作就会调用这个<code>update</code>方法）：<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">update(ownerID, shift, keyHash, key, value, didChangeSize, didAlter) &#123;</span><br><span class="line">  <span class="comment">// ...省略前面的代码</span></span><br><span class="line">  <span class="keyword">const</span> isEditable = ownerID &amp;&amp; ownerID === <span class="keyword">this</span>.ownerID;</span><br><span class="line">  <span class="keyword">const</span> newNodes = setAt(nodes, idx, newNode, isEditable);</span><br><span class="line"></span><br><span class="line">  <span class="keyword">if</span> (isEditable) &#123;</span><br><span class="line">    <span class="keyword">this</span>.count = newCount;</span><br><span class="line">    <span class="keyword">this</span>.nodes = newNodes;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">this</span>;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> <span class="keyword">new</span> HashArrayMapNode(ownerID, newCount, newNodes);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
与前面讲的逻辑一样，先比较该节点<code>ownerID</code>与传进来父节点的是否一致，然后直接在节点上操作或生成新的节点。</li>
</ol>
<h1 id="hash冲突"><a href="#hash冲突" class="headerlink" title="hash冲突"></a>hash冲突</h1><p>这块的内容就没什么新东西了，任何语言或库里对于 hashMap 的实现都需考虑到 hash 冲突的问题。我们主要看一下 Immutable.js 是怎么处理的。<br>要上一篇我们知道了，在往 Map 里存一对 key、value 时， Immutable.js 会先对 key 进行 hash ，根据 hash 后的值存到树的相应位置里。不同的 key 被 hash 后的结果是可能相同的，即便概率应当很小。<br>hash 冲突是一个很基本的问题，解决方法有很多，这里最简单适用的方法就是把冲突的节点扩展成一个线性结构，即数组，数组里直接存一组组 key 和 value ，查找到此处时则遍历该数组找到匹配的 key 。虽然这里的时间复杂度会变成线性的，但考虑到发生 hash 冲突的概率很低，所以时间复杂度的增加可以忽略不计。<br>我发现 Immutable.js 的 hash 函数对<code>abc</code>和<code>bCc</code>的 hash 结果都是 <code>96354</code>，在同一个 map 里用这两个 key 就会造成 hash 冲突，我们把这个 map log 出来如下：<br><img src="/2018/09/19/深入探究immutable.js的实现机制（二）/console.png" width="600"><br>Immutable.js 用了一个叫做<code>HashCollisionNode</code>的节点去处理发生冲突的键值，它们被放在<code>entries</code>数组里。<br>大家也可以自己试试，代码如下：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> map = <span class="keyword">new</span> Immutable.Map(&#123;&#125;);</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; <span class="number">10</span>; i++) &#123;</span><br><span class="line">  map = map.set(<span class="built_in">Math</span>.random(), i); <span class="comment">// 随便塞一点别的数据</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">map = map.set(<span class="string">'abc'</span>, <span class="string">'value1'</span>);</span><br><span class="line">map = map.set(<span class="string">'bCc'</span>, <span class="string">'value2'</span>);</span><br><span class="line"></span><br><span class="line"><span class="built_in">console</span>.log(map)</span><br></pre></td></tr></table></figure></p>
<blockquote>
<h3 id="参考："><a href="#参考：" class="headerlink" title="参考："></a>参考：</h3><p><a href="https://hypirion.com/musings/understanding-persistent-vector-pt-1" target="_blank" rel="noopener">https://hypirion.com/musings/understanding-persistent-vector-pt-1</a><br><a href="https://io-meter.com/2016/11/06/functional-go-intro-to-hamt" target="_blank" rel="noopener">https://io-meter.com/2016/11/06/functional-go-intro-to-hamt</a><br><a href="https://cdn.oreillystatic.com/en/assets/1/event/259/Immutable%20data%20structures%20for%20functional%20JavaScript%20Presentation.pdf" target="_blank" rel="noopener">https://cdn.oreillystatic.com/en/assets/1/event/259/Immutable%20data%20structures%20for%20functional%20JavaScript%20Presentation.pdf</a><br><a href="https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf" target="_blank" rel="noopener">https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf</a><br><a href="http://lampwww.epfl.ch/papers/idealhashtrees.pdf" target="_blank" rel="noopener">http://lampwww.epfl.ch/papers/idealhashtrees.pdf</a><br><a href="https://github.com/funfish/blog" target="_blank" rel="noopener">https://github.com/funfish/blog</a><br><a href="https://github.com/facebook/immutable-js/blob/e65e5af806ea23a32ccf8f56c6fabf39605bac80/src" target="_blank" rel="noopener">https://github.com/facebook/immutable-js/blob/e65e5af806ea23a32ccf8f56c6fabf39605bac80/src</a></p>
</blockquote>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2018/09/19/深入探究immutable.js的实现机制（二）/" data-id="cjt066zg1000de0z46b4cxp24" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/immutable-js-immutable-JavaScript-持久化数据结构-结构共享-bitmap-transient-hash冲突-Vector-Trie-Clojure/">immutable.js,immutable,JavaScript,持久化数据结构,结构共享,bitmap,transient,hash冲突,Vector Trie,Clojure</a></li></ul>

    </footer>
  </div>
  
</article>


  
    <article id="post-深入探究immutable.js的实现机制（一）" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2018/09/12/深入探究immutable.js的实现机制（一）/" class="article-date">
  <time datetime="2018-09-12T08:29:46.000Z" itemprop="datePublished">2018-09-12</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2018/09/12/深入探究immutable.js的实现机制（一）/">深入探究immutable.js的实现机制（一）</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>Immutable.js 由 Facebook 花费 3 年时间打造，为前端开发提供了很多便利，如今 React+Redux+Immutable.js 的组合已经成为许多项目的标配。我们知道 Immutable.js 采用了<code>持久化数据结构</code>和<code>结构共享</code>，保证每一个对象都是不可变的，任何添加、修改、删除等操作都会生成一个新的对象，且通过<code>结构共享</code>等方式大幅提高性能。<br>网上已经有很多文章简单介绍了 Immutable.js 的原理，但基本都是浅尝辄止，我也是搜了很久没找到针对 Immutable.js 原理的相对深入详细的文章，中英文都没有，针对 Clojure 或 Go 中持久化数据结构实现的文章倒是有一些。本文会集合多方资料以及我自己的一些理解，深入一些探究 Immutable.js 实现机制。<br>由于需要探讨的内容较长，写起来也比较费时，所以该系列会分成二到三篇文章完成。</p>
<blockquote>
<p>Immutable.js 部分参考了 Clojure 中的<code>PersistentVector</code>的实现方式，并有所优化和取舍，本文的一些内容也是基于它，想了解的可以阅读<a href="https://hypirion.com/musings/understanding-persistent-vector-pt-1" target="_blank" rel="noopener">这里</a>（共五篇，这是第一篇）</p>
</blockquote>
<h1 id="简单的例子"><a href="#简单的例子" class="headerlink" title="简单的例子"></a>简单的例子</h1><p>在深入研究前，我们先看个简单的例子：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> map1 = Immutable.Map(&#123;&#125;);</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; <span class="number">800</span>; i++) &#123;</span><br><span class="line">  map1 = map1.set(<span class="built_in">Math</span>.random(), <span class="built_in">Math</span>.random());</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="built_in">console</span>.log(map1);</span><br></pre></td></tr></table></figure><br>这段代码先后往map里写入了800对随机生成的key和value。我们先看一下控制台的输出结果，对它的数据结构有个大致的认知（粗略扫一眼就行了）：<br><img src="/2018/09/12/深入探究immutable.js的实现机制（一）/console截图.png" width="500"><br>可以看到这是一个树的结构，子节点以数组的形式放在<code>nodes</code>属性里，nodes的最大长度似乎是32个。了解过 bitmap 的人可能已经猜到了这里<code>bitmap</code>属性是做什么的，它涉及到对于树宽度的压缩，这些后面会说。<br>其中一个节点层层展开后长这样：<br><img src="/2018/09/12/深入探究immutable.js的实现机制（一）/console截图2.png" width="500"><br>这个<code>ValueNode</code>存的就是一组值了，<code>entry[0]</code>是key，<code>entry[1]</code>是value。</p>
<p>大致看个形状就行了，下面我们会由浅入深逐步揭开它的面纱。</p>
<h1 id="基本原理"><a href="#基本原理" class="headerlink" title="基本原理"></a>基本原理</h1><p>我们先看下维基对于<code>持久化数据结构</code>的定义：</p>
<blockquote>
<p>In computing, a persistent data structure is a data structure that always preserves the previous version of itself when it is modified.</p>
</blockquote>
<p>通俗点解释就是，对于一个<code>持久化数据结构</code>，每次修改后我们都会得到一个新的版本，且旧版本可以完好保留。</p>
<p>Immutable.js 用树实现了<code>持久化数据结构</code>，先看下图这颗树：<br><img src="/2018/09/12/深入探究immutable.js的实现机制（一）/tree1.png" width="300"><br>假如我们要在<code>g</code>下面插入一个节点<code>h</code>，如何在插入后让原有的树保持不变？最简单的方法当然是重新生成一颗树：<br><img src="/2018/09/12/深入探究immutable.js的实现机制（一）/tree2.png" width="350"><br>但这样做显然是很低效的，每次操作都需要生成一颗全新的树，既费时又费空间，因而有了如下的优化方案：<br><img src="/2018/09/12/深入探究immutable.js的实现机制（一）/tree3.png" width="300"><br>我们新生成一个根节点，对于有修改的部分，把相应路径上的所有节点重新生成，对于本次操作没有修改的部分，我们可以直接把相应的旧的节点拷贝过去，这其实就是<code>结构共享</code>。这样每次操作同样会获得一个全新的版本（根节点变了，新的<code>a</code>!==旧的<code>a</code>），历史版本可以完好保留，同时也节约了空间和时间。<br>至此我们发现，用树实现<code>持久化数据结构</code>还是比较简单的，Immutable.js提供了多种数据结构，比如回到开头的例子，一个map如何成为<code>持久化数据结构</code>呢？</p>
<h1 id="Vector-Trie"><a href="#Vector-Trie" class="headerlink" title="Vector Trie"></a>Vector Trie</h1><p>实际上对于一个map，我们完全可以把它视为一颗扁平的树，与上文实现<code>持久化数据结构</code>的方式一样，每次操作后生成一个新的对象，把旧的值全都依次拷贝过去，对需要修改或添加的属性，则重新生成。这其实就是<code>Object.assign</code>，然而这样显然效率很低，有没有更好的方法呢？<br>在实现<code>持久化数据结构</code>时，Immutable.js 参考了<code>Vector Trie</code>这种数据结构（其实更准确的叫法是<code>persistent bit-partitioned vector trie</code>或<code>bitmapped vector trie</code>，这是Clojure里使用的一种数据结构，Immutable.js 里的相关实现与其很相似），我们先了解下它的基本结构。<br>假如我们有一个 map ，key 全都是数字（当然你也可以把它理解为数组）<code>{0: ‘banana’, 1: ‘grape’, 2: ‘lemon’, 3: ‘orange’, 4: ‘apple’}</code>，为了构造一棵二叉<code>Vector Trie</code>，我们可以先把所有的key转换为二进制的形式：<code>{‘000’: ‘banana’, ‘001’: ‘grape’, ‘010’: ‘lemon’, ‘011’: ‘orange’, ‘100’: ‘apple’}</code>，然后如下图构建<code>Vector Trie</code>：<br><img src="/2018/09/12/深入探究immutable.js的实现机制（一）/vectorTrie1.png" width="300"><br>可以看到，<code>Vector Trie</code>的每个节点是一个数组，数组里有<code>0</code>和<code>1</code>两个数，表示一个二进制数，所有值都存在叶子节点上，比如我们要找<code>001</code>的值时，只需顺着<code>0</code> <code>0</code> <code>1</code>找下来，即可得到<code>grape</code>。那么想实现<code>持久化数据结构</code>当然也不难了，比如我们想添加一个<code>5: ‘watermelon’</code>：<br><img src="/2018/09/12/深入探究immutable.js的实现机制（一）/vectorTrie2.png" width="400"><br>可见对于一个 key 全是数字的map，我们完全可以通过一颗<code>Vector Trie</code>来实现它，同时实现<code>持久化数据结构</code>。如果key不是数字怎么办呢？转成数字就行了。 Immutable.js 实现了一个<a href="https://github.com/facebook/immutable-js/blob/e65e5af806ea23a32ccf8f56c6fabf39605bac80/src/Hash.js#L10:17" target="_blank" rel="noopener">hash</a>函数，可以把一个值转换成相应数字。<br>这里为了简化，每个节点数组长度仅为2，这样在数据量大的时候，树会变得很深，查询会很耗时，所以可以扩大数组的长度，Immutable.js 选择了32。为什么不是31？40？其实数组长度必须是2的整数次幂，这里涉及到实现<code>Vector Trie</code>时的一个优化，接下来我们先研究下这点。</p>
<h1 id="数字分区（Digit-partitioning）"><a href="#数字分区（Digit-partitioning）" class="headerlink" title="数字分区（Digit partitioning）"></a>数字分区（Digit partitioning）</h1><p><code>数字分区</code>指我们把一个 key 作为数字对应到一棵前缀树上，正如上节所讲的那样。<br>假如我们有一个 key <code>9128</code>，以 7 为基数，即数组长度是 7，它在<code>Vector Trie</code>里是这么表示的：<br><img src="/2018/09/12/深入探究immutable.js的实现机制（一）/base7.png" width="500"><br>需要5层数组，我们先找到<code>3</code>这个分支，再找到<code>5</code>，之后依次到<code>0</code>。为了依次得到这几个数字，我们可以预先把<code>9128</code>转为7进制的<code>35420</code>，但其实没有这个必要，因为转为 7 进制形式的过程就是不断进行除法并取余得到每一位上的数，我们无须预先转换好，类似的操作可以在每一层上依次执行。<br>运用进制转换相关的知识，我们可以采用这个方法<code>key / radix<sup>level - 1</sup> % radix</code>得到每一位的数（<strong>为了简便，本文除代码外所有<code>/</code>符号皆表示除法且向下取整</strong>），其中<code>radix</code>是每层数组的长度，即转换成几进制，<code>level</code>是当前在第几层，即第几位数。比如这里<code>key</code>是<code>9128</code>，<code>radix</code>是<code>7</code>，一开始<code>level</code>是<code>5</code>，通过这个式子我们可以得到第一层的数<code>3</code>。<br>代码实现如下：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> RADIX = <span class="number">7</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">find</span>(<span class="params">key</span>) </span>&#123;</span><br><span class="line">  <span class="keyword">let</span> node = root; <span class="comment">// root是根节点，在别的地方定义了</span></span><br><span class="line"></span><br><span class="line">  <span class="comment">// depth是当前树的深度。这种计算方式跟上面列出的式子是等价的，但可以避免多次指数计算</span></span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">let</span> size = <span class="built_in">Math</span>.pow(RADIX, (depth - <span class="number">1</span>)); size &gt; <span class="number">1</span>; size /= RADIX) &#123;</span><br><span class="line">    node = node[<span class="built_in">Math</span>.floor(key / size) % RADIX];</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> node[key % RADIX];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h1 id="位分区（Bit-Partitioning）"><a href="#位分区（Bit-Partitioning）" class="headerlink" title="位分区（Bit Partitioning）"></a>位分区（Bit Partitioning）</h1><p>显然，以上<code>数字分区</code>的方法是有点耗时的，在每一层我们都要进行两次除法一次取模，显然这样并不高效，<code>位分区</code>就是对其的一种优化。<br><code>位分区</code>实际上是<code>数字分区</code>的一个子集，所有以2的整数次幂（2，4，8，16，32…）为基数的<code>数字分区</code>前缀树，都可以转为<code>位分区</code>。基于一些位运算相关的知识，我们就能避免一些耗时的计算。<br><code>数字分区</code>把 key 拆分成一个个数字，而<code>位分区</code>把 key 分成一组组 bit。比如一个 32 路的前缀树，<code>数字分区</code>的方法是把 key 以 32 为基数拆分（实际上就是32进制），而<code>位分区</code>是把它以 5bit 拆分，实际上就是把 32 进制数的每一位看做 5 个 bit ，或者说把 32 进制数看做2进制进行操作，这样原本的很多计算就可以用更高效的位运算的方式代替。因为现在基数是 32，即<code>radix</code>为 32，所以前面的式子现在是<code>key / 32<sup>level - 1</sup> % 32</code>，而 32 又可以写作<code>2<sup>5</sup></code>，那么该式子可以转成这样<code>key / 2<sup>5 × (level - 1)</sup> % 2<sup>5</sup></code>。根据位运算相关的知识我们知道<code>a / 2<sup>n</sup> === a &gt;&gt;&gt; n </code>、<code>a % 2<sup>n</sup> === a &amp; (n - 1) </code>。<br><strong>如果你对位运算不太熟悉的话，大可不看上面的式子，举个例子就好理解了</strong>：比如数字<code>666666</code>的二进制形式是<code>10100 <strong>01011</strong> 00001 01010</code>，这是一个20位的二进制数。如果我们要得到第二层那五位数<code>01011</code>，我们可以先把它右移<code>&gt;&gt;&gt;</code>(左侧补0)10位，得到<code>00000 00000 10100 01011</code>，再<code>&amp;</code>一下<code>00000 00000 00000 11111</code>，就得到了<code>01011</code>。<br>这样我们可以得到下面的代码：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> SHIFT = <span class="number">5</span>;</span><br><span class="line"><span class="keyword">const</span> WIDTH = <span class="number">1</span> &lt;&lt; SHIFT, <span class="comment">//  32</span></span><br><span class="line"><span class="keyword">const</span> MASK = WIDTH - <span class="number">1</span>; <span class="comment">// 31，即11111</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">find</span>(<span class="params">key</span>) </span>&#123;</span><br><span class="line">  <span class="keyword">let</span> node = root; </span><br><span class="line"></span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">let</span> shift = (depth - <span class="number">1</span>) * SHIFT; shift &gt; <span class="number">0</span>; shift -= SHIFT) &#123;</span><br><span class="line">    node = node[(key &gt;&gt;&gt; shift) &amp; MASK];</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> node[key &amp; MASK];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><br>这样我们每次查找的速度就会得到提升。可以看一张图进行理解，为了简化展示，假设我们只有2位分区即4路的前缀树，对于<code>626</code>，我们的查找过程如下：<br><img src="/2018/09/12/深入探究immutable.js的实现机制（一）/base2.png" width="500"><br><code>626</code>的二进制形式是<code>10 01 11 00 10</code>，所以通过以上的位运算，我们便依次得到了<code>10</code>、<code>01</code>…</p>
<h1 id="源码"><a href="#源码" class="headerlink" title="源码"></a>源码</h1><p>说了这么多，我们看一下 Immutable.js 的源码吧。我们主要看一下查找的部分就够了，这是<code>Vector Trie</code>的核心。<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">get(shift, keyHash, key, notSetValue) &#123;</span><br><span class="line">  <span class="keyword">if</span> (keyHash === <span class="literal">undefined</span>) &#123;</span><br><span class="line">    keyHash = hash(key);</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">const</span> idx = (shift === <span class="number">0</span> ? keyHash : keyHash &gt;&gt;&gt; shift) &amp; MASK;</span><br><span class="line">  <span class="keyword">const</span> node = <span class="keyword">this</span>.nodes[idx];</span><br><span class="line">  <span class="keyword">return</span> node</span><br><span class="line">    ? node.get(shift + SHIFT, keyHash, key, notSetValue)</span><br><span class="line">    : notSetValue;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><br>可以看到， Immutable.js 也正是采用了位分区的方式，通过位运算得到当前数组的 index 选择相应分支。<br>不过它的实现方式与上文所讲的有一点不同，上文中对于一个 key ，我们是“正序”存储的，比如上图那个<code>626</code>的例子，我们是从根节点往下依次按照<code>10 01 11 00 10</code>去存储，而 Immutable.js 里则是“倒序”，按照<code>10 00 11 01 10</code>存储。所以通过源码这段你会发现 Immutable.js 查找时先得到的是 key 末尾的 SHIFT 个 bit ，然后再得到它们之前的 SHIFT 个 bit ，依次往前下去，而前面我们的代码是先得到 key 开头的 SHIFT 个 bit，依次往后。<br>用这种方式的原因之一是key的大小（二进制长度）不固定。</p>
<h1 id="时间复杂度"><a href="#时间复杂度" class="headerlink" title="时间复杂度"></a>时间复杂度</h1><p>因为采用了<code>结构共享</code>，在添加、修改、删除操作后，我们避免了将 map 中所有值拷贝一遍，所以特别是在数据量较大时，这些操作相比<code>Object.assign</code>有明显提升。<br>然而，查询速度似乎减慢了？我们知道 map 里根据 key 查找的速度是<code>O(1)</code>，这里由于变成了一棵树，查询的时间复杂度变成了<code>O(log N)</code>，准确说是<code>O(log<sub>32</sub> N)</code>。<br>等等 32 叉树？这棵树可不是一般地宽啊，Javascript里对象可以拥有的key的最大数量一般不会超过<code>2<sup>32</sup></code>个（<a href="http://www.ecma-international.org/ecma-262/5.1/#sec-15.4.2.2" target="_blank" rel="noopener">ECMA-262第五版</a>里定义了JS里由于数组的长度本身是一个 32 位数，所以数组长度不应大于 2<sup>32</sup> - 1 ，JS里对象的实现相对复杂，但大部分功能是建立在数组上的，所以在大部分场景下对象里 key 的数量不会超过 2<sup>32</sup> - 1。相关讨论见<a href="https://stackoverflow.com/questions/30194088/do-javascript-variables-have-a-storage-limit" target="_blank" rel="noopener">这里</a>），这样就可以把查找的时间复杂度当做是“<code>O(log<sub>32</sub> 2<sup>32</sup>)</code>”，差不多就是“<code>O(log 7)</code>”，所以我们可以认为在实际运用中，5bit (32路)的 Vector Trie 查询的时间复杂度是常数级的，32 叉树就是用了空间换时间。<br>空间…这个 32 叉树占用的空间也太大了吧？即便只有三层，我们也会有超过<code>32 × 32 × 32 = 32768</code>个节点。当然 Immutable.js 在具体实现时肯定不会傻乎乎的占用这么大空间，它对树的高度和宽度都做了“压缩”，此外，还对操作效率进行了其它一些优化，比如对 list 进行了“tail优化”。<strong>相关内容我们下一章讨论</strong>。</p>
<blockquote>
<h3 id="参考："><a href="#参考：" class="headerlink" title="参考："></a>参考：</h3><p><a href="https://hypirion.com/musings/understanding-persistent-vector-pt-1" target="_blank" rel="noopener">https://hypirion.com/musings/understanding-persistent-vector-pt-1</a><br><a href="https://io-meter.com/2016/09/03/Functional-Go-persist-datastructure-intro" target="_blank" rel="noopener">https://io-meter.com/2016/09/03/Functional-Go-persist-datastructure-intro</a><br><a href="https://cdn.oreillystatic.com/en/assets/1/event/259/Immutable%20data%20structures%20for%20functional%20JavaScript%20Presentation.pdf" target="_blank" rel="noopener">https://cdn.oreillystatic.com/en/assets/1/event/259/Immutable%20data%20structures%20for%20functional%20JavaScript%20Presentation.pdf</a><br><a href="https://michael.steindorfer.name/publications/oopsla15.pdf" target="_blank" rel="noopener">https://michael.steindorfer.name/publications/oopsla15.pdf</a><br><a href="https://github.com/facebook/immutable-js/blob/e65e5af806ea23a32ccf8f56c6fabf39605bac80/src" target="_blank" rel="noopener">https://github.com/facebook/immutable-js/blob/e65e5af806ea23a32ccf8f56c6fabf39605bac80/src</a></p>
</blockquote>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2018/09/12/深入探究immutable.js的实现机制（一）/" data-id="cjt066zg0000be0z4lrha2b3t" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/immutable-js-immutable-JavaScript-持久化数据结构-结构共享-Vector-Trie-Clojure/">immutable.js,immutable,JavaScript,持久化数据结构,结构共享,Vector Trie,Clojure</a></li></ul>

    </footer>
  </div>
  
</article>


  
    <article id="post-彻底搞懂https的加密机制" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2018/09/04/彻底搞懂https的加密机制/" class="article-date">
  <time datetime="2018-09-04T02:07:54.000Z" itemprop="datePublished">2018-09-04</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2018/09/04/彻底搞懂https的加密机制/">彻底搞懂HTTPS的加密机制</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>HTTPS的加密机制（SSL/TLS）虽然是个前端后端ios安卓等都应了解的基本问题，但不少人对它的了解都浮于表面，有很多关键机制没有彻底弄明白。网上的很多HTTPS相关文章也总会忽略一些内容，我学习它的时候也废了挺大功夫。<br>对称加密、非对称加密、数字签名、数字证书等等，在学习过程中，除了了解“它是什么”，你是否有想过“为什么是它”、“为什么不是xxx”？我认为理解了后两个问题才真正理解了HTTPS的加密机制。<br>本文以问题的形式逐步展开，一步步解开HTTPS的面纱，希望能帮助你彻底搞懂HTTPS。特别是对于了解过HTTPS却在有些地方有所卡壳的人，希望本文能帮助你理清思路。</p>
<h2 id="为什么需要加密？"><a href="#为什么需要加密？" class="headerlink" title="为什么需要加密？"></a>为什么需要加密？</h2><p>因为http的内容是明文传输的，明文数据会经过中间代理服务器、路由器、wifi热点、通信服务运营商等多个物理节点，如果信息在传输过程中被劫持，传输的内容就完全暴露了，他还可以篡改传输的信息且不被双方察觉，这就是<code>中间人攻击</code>。所以我们才需要对信息进行加密。</p>
<h2 id="什么是对称加密？"><a href="#什么是对称加密？" class="headerlink" title="什么是对称加密？"></a>什么是对称加密？</h2><p>就是有一个密钥，它可以对一段内容加密，加密后只能用它才能解密看到原本的内容，就和我们日常生活中用的钥匙作用一样。</p>
<h2 id="用对称加密可行吗？"><a href="#用对称加密可行吗？" class="headerlink" title="用对称加密可行吗？"></a>用对称加密可行吗？</h2><p><strong>如果通信双方都各自持有同一个密钥，且没有别人知道，这两方的通信安全当然是可以被保证的（除非密钥被破解）。</strong><br>然而最大的问题就是<strong>这个密钥怎么让传输的双方知晓，同时不被别人知道</strong>。如果由服务器生成一个密钥并传输给浏览器，那这个传输过程中密钥被别人劫持弄到手了怎么办？之后他就能用密钥解开双方传输的任何内容了，所以这么做当然不行。<br>换种思路？试想一下，如果浏览器内部就预存了网站A的密钥，且可以确保除了浏览器和网站A，不会有任何外人知道该密钥，那理论上用对称加密是可以的，这样浏览器只要预存好世界上所有HTTPS网站的密钥就行啦！这么做显然不现实。（那在自己的ios或安卓的app里预先藏入自己服务器的密钥，通过对称加密的方式与服务器通信可以吗？我认为一般是可以的，但是一定要对密钥做好防护）<br>怎么办？所以我们就需要神奇的<code>非对称加密</code></p>
<h2 id="什么是非对称加密？"><a href="#什么是非对称加密？" class="headerlink" title="什么是非对称加密？"></a>什么是非对称加密？</h2><p>有两把密钥，通常一把叫做公钥、一把叫做私钥，用公钥加密的内容必须用私钥才能解开，同样，私钥加密的内容只有公钥能解开。</p>
<h2 id="用非对称加密可行吗？"><a href="#用非对称加密可行吗？" class="headerlink" title="用非对称加密可行吗？"></a>用非对称加密可行吗？</h2><p>鉴于非对称加密的机制，我们可能会有这种思路：服务器先把公钥直接明文传输给浏览器，之后浏览器向服务器传数据前都先用这个公钥加密好再传，这条数据的安全似乎可以保障了！<strong>因为只有服务器有相应的私钥能解开这条数据</strong>。<br>然而<strong>由服务器到浏览器的这条路怎么保障安全？</strong>如果服务器用它的的私钥加密数据传给浏览器，那么浏览器用公钥可以解密它，而这个公钥是一开始通过明文传输给浏览器的，这个公钥被谁劫持到的话，他也能用该公钥解密服务器传来的信息了。所以<strong>目前似乎只能保证由浏览器向服务器传输数据时的安全性</strong>（其实仍有漏洞，下文会说），那利用这点你能想到什么解决方案吗？</p>
<h2 id="改良的非对称加密方案，似乎可以？"><a href="#改良的非对称加密方案，似乎可以？" class="headerlink" title="改良的非对称加密方案，似乎可以？"></a>改良的非对称加密方案，似乎可以？</h2><p>我们已经理解通过一组公钥私钥，已经可以保证单个方向传输的安全性，那用两组公钥私钥，是不是就能保证双向传输都安全了？请看下面的过程：</p>
<ol>
<li>某网站拥有用于非对称加密的公钥A、私钥A’；浏览器拥有用于非对称加密的公钥B、私钥B’。</li>
<li>浏览器像网站服务器请求，服务器把公钥A明文给传输浏览器。</li>
<li>浏览器把公钥B明文传输给服务器。</li>
<li>之后浏览器向服务器传输的所有东西都用公钥A加密，服务器收到后用私钥A’解密。由于只有服务器拥有这个私钥A’可以解密，所以能保证这条数据的安全。</li>
<li>服务器向浏览器传输的所有东西都用公钥B加密，浏览器收到后用私钥B’解密。同上也可以保证这条数据的安全。</li>
</ol>
<p>的确可以！抛开这里面仍有的漏洞不谈（下文会讲），HTTPS的加密却没使用这种方案，为什么？最主要的原因是非对称加密算法非常耗时，特别是加密解密一些较大数据的时候有些力不从心，而对称加密快很多，看来必须得用对称加密，那我们能不能运用非对称加密的特性解决前面提到的对称加密的问题？</p>
<h2 id="非对称加密-对称加密？"><a href="#非对称加密-对称加密？" class="headerlink" title="非对称加密+对称加密？"></a>非对称加密+对称加密？</h2><p>既然非对称加密耗时，非对称加密+对称加密结合可以吗？而且得尽量减少非对称加密的次数。当然是可以的，而且非对称加密、解密各只需用一次即可。<br>请看一下这个过程：</p>
<ol>
<li>某网站拥有用于非对称加密的公钥A、私钥A’。</li>
<li>浏览器像网站服务器请求，服务器把公钥A明文给传输浏览器。</li>
<li>浏览器随机生成一个用于对称加密的密钥X，用公钥A加密后传给服务器。</li>
<li>服务器拿到后用私钥A’解密得到密钥X。</li>
<li>这样双方就都拥有密钥X了，且别人无法知道它。之后双方所有数据都用密钥X加密解密。</li>
</ol>
<p>完美！HTTPS基本就是采用了这种方案。完美？还是有漏洞的。</p>
<h2 id="中间人攻击"><a href="#中间人攻击" class="headerlink" title="中间人攻击"></a>中间人攻击</h2><p>中间人的确无法得到浏览器生成的密钥B，这个密钥本身被公钥A加密了，只有服务器才有私钥A’解开拿到它呀！然而中间人却完全不需要拿到密钥A’就能干坏事了。请看：</p>
<ol>
<li>某网站拥有用于非对称加密的公钥A、私钥A’。</li>
<li>浏览器向网站服务器请求，服务器把公钥A明文给传输浏览器。</li>
<li><strong>中间人劫持到公钥A，保存下来，把数据包中的公钥A替换成自己伪造的公钥B（它当然也拥有公钥B对应的私钥B’）</strong>。</li>
<li>浏览器随机生成一个用于对称加密的密钥X，用<strong>公钥B</strong>（浏览器不知道公钥被替换了）加密后传给服务器。</li>
<li><strong>中间人劫持后用私钥B’解密得到密钥X，再用公钥A加密后传给服务器</strong>。</li>
<li>服务器拿到后用私钥A’解密得到密钥X。</li>
</ol>
<p>这样在双方都不会发现异常的情况下，中间人得到了密钥B。<strong>根本原因是浏览器无法确认自己收到的公钥是不是网站自己的</strong>。那么下一步就是解决下面这个问题：</p>
<h2 id="如何证明浏览器收到的公钥一定是该网站的公钥？"><a href="#如何证明浏览器收到的公钥一定是该网站的公钥？" class="headerlink" title="如何证明浏览器收到的公钥一定是该网站的公钥？"></a>如何证明浏览器收到的公钥一定是该网站的公钥？</h2><p>现实生活中，如果想证明某身份证号一定是小明的，怎么办？看身份证。这里政府机构起到了“公信”的作用，身份证是由它颁发的，它本身的权威可以对一个人的身份信息作出证明。互联网中能不能搞这么个公信机构呢？给网站颁发一个“身份证”？</p>
<h2 id="数字证书"><a href="#数字证书" class="headerlink" title="数字证书"></a>数字证书</h2><p>网站在使用HTTPS前，需要向“<strong>CA机构</strong>”申请颁发一份<strong>数字证书</strong>，数字证书里有证书持有者、证书持有者的公钥等信息，服务器把证书传输给浏览器，浏览器从证书里取公钥就行了，证书就如身份证一样，可以证明“该公钥对应该网站”。然而这里又有一个显而易见的问题了，证书本身的传输过程中，如何防止被篡改？即如何证明证书本身的真实性？身份证有一些防伪技术，数字证书怎么防伪呢？解决这个问题我们就基本接近胜利了！</p>
<h2 id="如何放防止数字证书被篡改？"><a href="#如何放防止数字证书被篡改？" class="headerlink" title="如何放防止数字证书被篡改？"></a>如何放防止数字证书被篡改？</h2><p>我们把证书内容生成一份“签名”，比对证书内容和签名是否一致就能察觉是否被篡改。这种技术就叫<code>数字签名</code>：</p>
<h2 id="数字签名"><a href="#数字签名" class="headerlink" title="数字签名"></a>数字签名</h2><p>这部分内容建议看下图并结合后面的文字理解，图中左侧是数字签名的制作过程，右侧是验证过程（原图出处找不到了，可以看出来这图已经被转载了无数次了。。。）<br><img src="/2018/09/04/彻底搞懂https的加密机制/数字签名.jpg" width="500"></p>
<p>数字签名的制作过程：</p>
<ol>
<li>CA拥有非对称加密的私钥和公钥。</li>
<li>CA对证书明文信息进行hash。</li>
<li>对hash后的值用私钥加密，得到数字签名。</li>
</ol>
<p>明文和数字签名共同组成了数字证书，这样一份数字证书就可以颁发给网站了。<br>那浏览器拿到服务器传来的数字证书后，如何验证它是不是真的？（有没有被篡改、掉包）</p>
<p>浏览器验证过程：</p>
<ol>
<li>拿到证书，得到明文T，数字签名S。</li>
<li>用CA机构的公钥对S解密（由于是浏览器信任的机构，所以浏览器保有它的公钥。详情见下文），得到S’。</li>
<li>用证书里说明的hash算法对明文T进行hash得到T’。</li>
<li>比较S’是否等于T’，等于则表明证书可信。</li>
</ol>
<p>为什么这样可以证明证书可信呢？我们来仔细想一下。</p>
<h2 id="中间人有可能篡改该证书吗？"><a href="#中间人有可能篡改该证书吗？" class="headerlink" title="中间人有可能篡改该证书吗？"></a>中间人有可能篡改该证书吗？</h2><p>假设中间人篡改了证书的原文，由于他没有CA机构的私钥，所以无法得到此时加密后签名，无法相应地篡改签名。浏览器收到该证书后会发现原文和签名解密后的值不一致，则说明证书已被篡改，证书不可信，从而终止向服务器传输信息，防止信息泄露给中间人。<br>既然不可能篡改，那整个证书被掉包呢？</p>
<h2 id="中间人有可能把证书掉包吗？"><a href="#中间人有可能把证书掉包吗？" class="headerlink" title="中间人有可能把证书掉包吗？"></a>中间人有可能把证书掉包吗？</h2><p>假设有另一个网站B也拿到了CA机构认证的证书，它想搞垮网站A，想劫持网站A的信息。于是它成为中间人拦截到了A传给浏览器的证书，然后替换成自己的证书，传给浏览器，之后浏览器就会错误地拿到B的证书里的公钥了，会导致上文提到的漏洞。<br>其实这并不会发生，因为证书里包含了网站A的信息，包括域名，浏览器把证书里的域名与自己请求的域名比对一下就知道有没有被掉包了。</p>
<h2 id="为什么制作数字签名时需要hash一次？"><a href="#为什么制作数字签名时需要hash一次？" class="headerlink" title="为什么制作数字签名时需要hash一次？"></a>为什么制作数字签名时需要hash一次？</h2><p>我初学HTTPS的时候就有这个问题，似乎以上过程中hash有点多余，把hash过程去掉也能保证证书没有被篡改。<br>最显然的是性能问题，前面我们已经说了非对称加密效率较差，证书信息一般较长，比较耗时。而hash后得到的是固定长度的信息（比如用md5算法hash后可以得到固定的128位的值），这样加密解密就会快很多。<br>当然还有安全上的原因，这部分内容相对深一些，感兴趣的可以看这篇解答：<a href="https://crypto.stackexchange.com/a/12780" target="_blank" rel="noopener">https://crypto.stackexchange.com/a/12780</a></p>
<h2 id="怎么证明CA机构的公钥是可信的？"><a href="#怎么证明CA机构的公钥是可信的？" class="headerlink" title="怎么证明CA机构的公钥是可信的？"></a>怎么证明CA机构的公钥是可信的？</h2><p>你们可能会发现上文中说到CA机构的公钥，我几乎一笔带过，“浏览器保有它的公钥”，这是个什么保有法？怎么证明这个公钥是否可信？<br>让我们回想一下数字证书到底是干啥的？没错，为了证明某公钥是可信的，即“该公钥是否对应该网站/机构等”，那这个CA机构的公钥是不是也可以用数字证书来证明？没错，操作系统、浏览器本身会预装一些它们信任的根证书，如果其中有该CA机构的根证书，那就可以拿到它对应的可信公钥了。</p>
<blockquote>
<p>实际上证书之间的认证也可以不止一层，可以A信任B，B信任C，以此类推，我们把它叫做<code>信任链</code>或<code>数字证书链</code>，也就是一连串的数字证书，由根证书为起点，透过层层信任，使终端实体证书的持有者可以获得转授的信任，以证明身份。</p>
</blockquote>
<p>另外，不知你们是否遇到过网站访问不了、提示要安装证书的情况？这里安装的就是跟证书。说明浏览器不认给这个网站颁发证书的机构，那么没有该机构的根证书，你就得手动下载安装（风险自己承担XD）。安装该机构的根证书后，你就有了它的公钥，就可以用它验证服务器发来的证书是否可信了。</p>
<h2 id="HTTPS必须在每次请求中都要先在SSL-TLS层进行握手传输密钥吗？"><a href="#HTTPS必须在每次请求中都要先在SSL-TLS层进行握手传输密钥吗？" class="headerlink" title="HTTPS必须在每次请求中都要先在SSL/TLS层进行握手传输密钥吗？"></a>HTTPS必须在每次请求中都要先在SSL/TLS层进行握手传输密钥吗？</h2><p>这也是我当时的困惑之一，显然每次请求都经历一次密钥传输过程非常耗时，那怎么达到只传输一次呢？用session就行。<br>服务器会为每个浏览器（或客户端软件）维护一个session ID，在TSL握手阶段传给浏览器，浏览器生成好密钥传给服务器后，服务器会把该密钥存到相应的session ID下，之后浏览器每次请求都会携带session ID，服务器会根据session ID找到相应的密钥并进行解密加密操作，这样就不必要每次重新制作、传输密钥了！</p>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>至此，我们已自下而上地打通了HTTPS加密的整个脉络以及核心知识点，不知你是否真正搞懂了HTTPS呢？<br>找几个时间，多看、多想、多理解几次就会越来越清晰的！</p>
<p>那么，下面的问题你是否已经可以解答了呢？</p>
<ol>
<li>为什么要用对称加密+非对称加密？</li>
<li>为什么不能只用非对称加密？</li>
<li>为什么需要数字证书？</li>
<li>为什么需要数字签名？<br>…</li>
</ol>
<p>这篇文章也是对我学习时的一些总结和我自己的理解，希望也能给你一些收获~</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2018/09/04/彻底搞懂https的加密机制/" data-id="cjt066zfz000ae0z42t8kwic7" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/HTTPS-SSL-TLS-加密-对称加密-非对称加密-数字证书-数字签名/">HTTPS,SSL,TLS,加密,对称加密,非对称加密,数字证书,数字签名</a></li></ul>

    </footer>
  </div>
  
</article>


  
    <article id="post-彻底搞懂white-space、word-break、word-wrap" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2018/08/31/彻底搞懂white-space、word-break、word-wrap/" class="article-date">
  <time datetime="2018-08-31T06:08:36.000Z" itemprop="datePublished">2018-08-31</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2018/08/31/彻底搞懂white-space、word-break、word-wrap/">彻底搞懂white-space、word-break、word-wrap</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>white-space、word-break、word-wrap（overflow-wrap）估计是css里最基本又最让人迷惑的三个属性了，我也是经常搞混，所以今天我们就把这三个属性彻底搞清楚。</p>
<h2 id="测试代码"><a href="#测试代码" class="headerlink" title="测试代码"></a>测试代码</h2><p><strong>(文末有本文中所有例子的代码)</strong><br>下面是本文中用于测试各个样式展现情况的html代码：<br><figure class="highlight html"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="tag">&lt;<span class="name">div</span> <span class="attr">id</span>=<span class="string">"box"</span>&gt;</span></span><br><span class="line">  Hi&amp;nbsp;&amp;nbsp;,</span><br><span class="line">  This   is a incomprehensibilities long word.</span><br><span class="line">  <span class="tag">&lt;/<span class="name">br</span>&gt;</span></span><br><span class="line">  你好&amp;nbsp;&amp;nbsp;，</span><br><span class="line">  这   是一个不可思议的长单词</span><br><span class="line"><span class="tag">&lt;/<span class="name">div</span>&gt;</span></span><br></pre></td></tr></table></figure><br>现在只给了它一个宽度和边框，没有其它任何样式，下面是它目前的展现情况：<br><img src="/2018/08/31/彻底搞懂white-space、word-break、word-wrap/init.png" class="myImg" width="180"><br>可以看到，<code>nbsp;</code>和<code>&lt;/br&gt;</code>可以正常发挥作用，而连续的空格会被缩减成一个（比如This和is之间的三个空格），换行符也全都无效。句子超过一行后会自动换行，而长度超过一行的单个单词会超出边界。<br>接下来我们看下， 给它上面三个css属性赋值后会出现什么变化。</p>
<h2 id="white-space"><a href="#white-space" class="headerlink" title="white-space"></a>white-space</h2><p>正如它的名字，<strong>这个属性是用来控制空白字符的显示的</strong>，同时还能控制是否自动换行。它有五个值：<code>normal | nowrap | pre | pre-wrap | pre-line</code>。因为默认是<code>normal</code>，所以我们主要研究下其它四种值时的展现情况。</p>
<p>（为了方便比较，下文所有图，左侧为<code>normal</code>即初始情况，右侧为赋上相应值时的情况）</p>
<p>先看下<code>white-space:nowrap</code>时的情况：</p>
<img src="/2018/08/31/彻底搞懂white-space、word-break、word-wrap/white-space_nowrap.png" width="500">
<p>不仅空格被合并，换行符无效，连原本的自动换行都没了！只有<code>&lt;/br&gt;</code>才能导致换行！所以这个值的表现还是挺简单的，我们可以理解为<code>永不换行</code>。</p>
<p><code>white-space:pre</code>：</p>
<img src="/2018/08/31/彻底搞懂white-space、word-break、word-wrap/white-space_pre.png" width="500">
<p>空格和换行符全都被保留了下来！不过自动换行还是没了。保留，所以<code>pre</code>其实是<code>preserve</code>的缩写，这样就好记了。</p>
<p><code>white-space:pre-wrap</code>：</p>
<img src="/2018/08/31/彻底搞懂white-space、word-break、word-wrap/white-space_pre-wrap.png" width="335">
<p>显然<code>pre-wrap</code>就是<code>preserve</code>+<code>wrap</code>，保留空格和换行符，且可以自动换行。</p>
<p><code>white-space:pre-line</code>：</p>
<img src="/2018/08/31/彻底搞懂white-space、word-break、word-wrap/white-space_pre-line.png" width="335">
<p>空格被合并了，但是换行符可以发挥作用，<code>line</code>应该是<code>new line</code>的意思，自动换行还在，所以<code>pre-line</code>其实是<code>preserve</code>+<code>new line</code>+<code>wrap</code>。</p>
<p><strong>我整理了一个表予以总结：</strong></p>
<table>
<thead>
<tr>
<th>是否能发挥作用</th>
<th>换行符</th>
<th>空格</th>
<th>自动换行</th>
<th>&lt;/br&gt;、nbsp;</th>
</tr>
</thead>
<tbody>
<tr>
<td>normal</td>
<td>×</td>
<td>×（合并）</td>
<td>√</td>
<td>√</td>
</tr>
<tr>
<td>nowrap</td>
<td>×</td>
<td>×（合并）</td>
<td>×</td>
<td>√</td>
</tr>
<tr>
<td>pre</td>
<td>√</td>
<td>√</td>
<td>×</td>
<td>√</td>
</tr>
<tr>
<td>pre-wrap</td>
<td>√</td>
<td>√</td>
<td>√</td>
<td>√</td>
</tr>
<tr>
<td>pre-line</td>
<td>√</td>
<td>×（合并）</td>
<td>√</td>
<td>√</td>
</tr>
</tbody>
</table>
<h2 id="word-break"><a href="#word-break" class="headerlink" title="word-break"></a>word-break</h2><p>从这个名字可以知道，<strong>这个属性是控制单词如何被拆分换行的</strong>。它有三个值：<code>normal | break-all | keep-all</code>。</p>
<p><code>word-break:keep-all</code>：</p>
<img src="/2018/08/31/彻底搞懂white-space、word-break、word-wrap/word-break_keep-all.png" width="355">
<p><strong>所有“单词”一律不拆分换行</strong>，注意，我这里的“单词”包括连续的中文字符（还有日文、韩文等），或者可以理解为<strong>只有空格可以触发自动换行</strong></p>
<p><code>word-break:break-all</code>：</p>
<img src="/2018/08/31/彻底搞懂white-space、word-break、word-wrap/word-break_break-all.png" width="320">
<p><strong>所有单词碰到边界一律拆分换行</strong>，不管你是<code>incomprehensibilities</code>这样一行都显示不下的单词，还是<code>long</code>这样很短的单词，只要碰到边界，都会被强制拆分换行。所以用<code>word-break:break-all</code>时要慎重呀。<br>这样的效果好像并不太好呀，能不能就把incomprehensibilities拆一下，其它的单词不拆呢？那就需要下面这个属性了：</p>
<h2 id="word-wrap（overflow-wrap）"><a href="#word-wrap（overflow-wrap）" class="headerlink" title="word-wrap（overflow-wrap）"></a>word-wrap（overflow-wrap）</h2><p><code>word-wrap</code>又叫做<code>overflow-wrap</code>：</p>
<blockquote>
<p>word-wrap 属性原本属于微软的一个私有属性，在 CSS3 现在的文本规范草案中已经被重名为 overflow-wrap 。 word-wrap 现在被当作 overflow-wrap 的 “别名”。 稳定的谷歌 Chrome 和 Opera 浏览器版本支持这种新语法。 </p>
</blockquote>
<p><strong>这个属性也是控制单词如何被拆分换行的</strong>，实际上是作为<code>word-break</code>的互补，它只有两个值：<code>normal | break-word</code>，那我们看下<code>break-word</code>：</p>
<img src="/2018/08/31/彻底搞懂white-space、word-break、word-wrap/word-wrap_break-word.png" width="320">
<p>终于达到了上文我们希望的效果，<strong>只有当一个单词一整行都显示不下时，才会拆分换行该单词</strong>。<br>所以我觉得<code>overflow-wrap</code>更好理解好记一些，overflow，只有长到溢出的单词才会被强制换行！</p>
<p>（其实前面的<code>word-break</code>属性除了列出的那三个值外，也有个<code>break-word</code>值，效果跟这里的<code>word-wrap:break-word</code>一样，然而只有Chrome、Safari等部分浏览器支持）</p>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>最后总结一下三个属性</p>
<ul>
<li>white-space，<strong>控制空白字符的显示</strong>，同时还能控制是否自动换行。它有五个值：<code>normal | nowrap | pre | pre-wrap | pre-line</code></li>
<li>word-break，<strong>控制单词如何被拆分换行</strong>。它有三个值：<code>normal | break-all | keep-all</code></li>
<li>word-wrap（overflow-wrap）<strong>控制长度超过一行的单词是否被拆分换行</strong>，是<code>word-break</code>的补充，它只有两个值：<code>normal | break-word</code></li>
</ul>
<p>相信读完了本文，你应该对white-space、word-break、word-wrap有比较系统的认识了吧，如果短时间还是记不住，常看一看就能记住的~</p>
<p><br></p>
<p>下面是本文里所有例子的代码的地址，每个属性做成了选项，方便操作学习~</p>
<iframe id="cp_embed_jvyrWK" src="//codepen.io/YGYOOO/embed/jvyrWK?height=400&theme-id=dark&slug-hash=jvyrWK&default-tab=html,result" scrolling="no" frameborder="no" height="400" allowtransparency="true" allowfullscreen="true" class="cp_embed_iframe" style="width: 100%; overflow: hidden;"></iframe>
      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2018/08/31/彻底搞懂white-space、word-break、word-wrap/" data-id="cjt066zfq0004e0z4gpkkl8vk" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/css-white-space-word-break-word-wrap-html/">css,white-space,word-break,word-wrap,html</a></li></ul>

    </footer>
  </div>
  
</article>


  
    <article id="post-JavaScript-使用WeakMap创建私有属性" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2018/08/28/JavaScript-使用WeakMap创建私有属性/" class="article-date">
  <time datetime="2018-08-28T02:58:49.000Z" itemprop="datePublished">2018-08-28</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2018/08/28/JavaScript-使用WeakMap创建私有属性/">JavaScript-使用WeakMap创建对象的私有属性</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>我们都知道JavaScript本身并没有共有、私有属性的概念，不过我们可以通过一些方式实现私有属性。<br>WeakMap也是ES6里就有了，不过我曾一直不太了解它的应用场景，看到有文章说用它的应用场景之一是实现私有属性。怎么实现？为何要用它实现？<br>关于用WeakMap实现私有属性的方式，本文会<strong>从它最原始的面貌看起，理解使用WeakMap的意义</strong>。</p>
<h2 id="闭包-可行吗？"><a href="#闭包-可行吗？" class="headerlink" title="闭包-可行吗？"></a>闭包-可行吗？</h2><p>提到“私有”的实现方式，我的第一反应就是闭包，似乎可行：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> Person = (<span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">let</span> name;</span><br><span class="line"></span><br><span class="line">  <span class="function"><span class="keyword">function</span> <span class="title">Person</span>(<span class="params">n</span>) </span>&#123;</span><br><span class="line">      name = n;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  Person.prototype.getName = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">      <span class="keyword">return</span> name;</span><br><span class="line">  &#125;;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> Person;</span><br><span class="line">&#125;());</span><br></pre></td></tr></table></figure><br>这样我们只要</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> person1 = <span class="keyword">new</span> Person(<span class="string">'小明'</span>);</span><br></pre></td></tr></table></figure>  
<p>这样<code>person1</code>就有它的私有<code>name</code>属性了，外部无法直接访问或修改改属性。等等，似乎有什么问题，如果我们再实例化一次<code>Person</code>呢？<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> person1 = <span class="keyword">new</span> Person(<span class="string">'小明'</span>);</span><br><span class="line"><span class="keyword">let</span> person2 = <span class="keyword">new</span> Person(<span class="string">'大明'</span>);</span><br><span class="line"><span class="built_in">console</span>.log(person1.getName()); <span class="comment">// 大明</span></span><br></pre></td></tr></table></figure><br>小明变成了大明！<code>person1</code>的<code>name</code>属性被覆盖了，所以这种方式实现的私有属性，实际上是被所有实例共享的，如果需要每个实例单独拥有自己的私有属性，这种方法就不行了。</p>
<h2 id="改进"><a href="#改进" class="headerlink" title="改进"></a>改进</h2><p>为了让每个实例拥有自己的私有属性，相互之间不影响，我们可以引入一个id作为每个实例的唯一标识，这样就实现了真正的私有属性：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> Person = (<span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">const</span> private = &#123;&#125;;</span><br><span class="line">  <span class="keyword">let</span> privateId = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">  <span class="function"><span class="keyword">function</span> <span class="title">Person</span>(<span class="params">name</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">this</span>._privateId = privateId++;</span><br><span class="line">    private[<span class="keyword">this</span>._privateId] = &#123;&#125;;</span><br><span class="line">    private[<span class="keyword">this</span>._privateId].name = name;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  Person.prototype.getName = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">      <span class="keyword">return</span> private[<span class="keyword">this</span>._privateId].name;</span><br><span class="line">  &#125;;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> Person;</span><br><span class="line">&#125;());</span><br><span class="line"></span><br><span class="line"><span class="keyword">let</span> person1 = <span class="keyword">new</span> Person(<span class="string">'小明'</span>);</span><br><span class="line"><span class="keyword">let</span> person2 = <span class="keyword">new</span> Person(<span class="string">'大明'</span>);</span><br><span class="line"><span class="built_in">console</span>.log(person1.getName()); <span class="comment">// 小明</span></span><br></pre></td></tr></table></figure><br>不过这样仍然有隐患，实例化后我们还是能更改其<code>_privateId</code>属性的值，一旦它被更改，私有属性就获取不到了。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">person1._privateId = <span class="number">111</span>;</span><br><span class="line"><span class="built_in">console</span>.log(person1.getName()); <span class="comment">// 报错</span></span><br></pre></td></tr></table></figure>
<p>所以我们改为用<code>Object.defineProperty</code>方法申明<code>_private</code>属性，防止它被更改。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">Object</span>.defineProperty(<span class="keyword">this</span>, <span class="string">'_privateId'</span>, &#123;</span><br><span class="line">  value: privateId++,</span><br><span class="line">  writable: <span class="literal">false</span>, <span class="comment">// 设为不可写，_privateId就不会被更改了（其实默认就是false）</span></span><br><span class="line">&#125;);</span><br><span class="line"><span class="keyword">this</span>._privateId = privateId++;</span><br><span class="line">private[<span class="keyword">this</span>._privateId] = &#123;&#125;;</span><br><span class="line">private[<span class="keyword">this</span>._privateId].name = name;</span><br></pre></td></tr></table></figure>
<p>至此，我们仅用es5的特性就实现了私有属性，而然该方法还有以下几个弊端：</p>
<ul>
<li>即便<code>Person</code>的某个实例对象被垃圾回收了，<code>private</code>对象里存储的它的全部私有属性依旧不会被回收，这会导致内存泄漏问题</li>
<li>每个实例对象多出了一个<code>_privateId</code>属性，而且该方法不够直观优雅</li>
</ul>
<h2 id="WeakMap了解一下？"><a href="#WeakMap了解一下？" class="headerlink" title="WeakMap了解一下？"></a>WeakMap了解一下？</h2><p>既然我们不想多造一个单独的<code>_privateId</code>属性去实现私有属性的存储，那还有什么值可以作为该实例对象的唯一标识呢？它的内存地址？可是js似乎不允许直接获取一个对象的地址。直接拿对象本身作为key可以吗？<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">private[<span class="keyword">this</span>] = &#123;&#125;;</span><br><span class="line">private[<span class="keyword">this</span>].name = name;</span><br></pre></td></tr></table></figure><br>这么写在语法上当然没问题，但实际上一个对象的key只能是字符串或Symbol，因而所有对象都会被转为同一段符串“[object Object]”（<code>private[this] = {}</code>实际上就是<code>private[‘[object Object]’] = {}</code>），所以这种方法当然不行。<br>而ES6的Map和WeakMap是可以将对象作为key的（WeakMap的key只能是对象）。那我们用WeakMap试一下？</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> Person = (<span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">const</span> private = <span class="keyword">new</span> <span class="built_in">WeakMap</span>();</span><br><span class="line"></span><br><span class="line">  <span class="function"><span class="keyword">function</span> <span class="title">Person</span>(<span class="params">name</span>) </span>&#123;</span><br><span class="line">    private.set(<span class="keyword">this</span>, &#123;&#125;);</span><br><span class="line">    private.get(<span class="keyword">this</span>).name = name;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  Person.prototype.getName = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">      <span class="keyword">return</span> private.get(<span class="keyword">this</span>).name;</span><br><span class="line">  &#125;;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> Person;</span><br><span class="line">&#125;());</span><br><span class="line"></span><br><span class="line"><span class="keyword">let</span> person1 = <span class="keyword">new</span> Person(<span class="string">'小明'</span>);</span><br><span class="line"><span class="keyword">let</span> person2 = <span class="keyword">new</span> Person(<span class="string">'大明'</span>);</span><br><span class="line"><span class="built_in">console</span>.log(person1.getName()); <span class="comment">// 小明</span></span><br></pre></td></tr></table></figure>
<p>现在代码看上去简单优雅了很多，我们不再需要额外的id去标识每个实例，那内存泄漏问题呢？这就是为何要用WeakMap而不是Map了，WeakMap对key对象仅有“弱引用”，当没有其它引用指向该key对象时，该对象即可被垃圾回收，WeakMap不会阻止回收。</p>
<p>其实用WeakMap实现私有属性本身是比较简单的，但了解其背后的原因和原理更加重要。</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2018/08/28/JavaScript-使用WeakMap创建私有属性/" data-id="cjt066zfn0003e0z4wywbmvnt" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/JavaScript-WeakMap-ES6/">JavaScript,WeakMap,ES6</a></li></ul>

    </footer>
  </div>
  
</article>


  


</section>
        
          <aside id="sidebar">
  
    

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/HTTPS-SSL-TLS-加密-对称加密-非对称加密-数字证书-数字签名/">HTTPS,SSL,TLS,加密,对称加密,非对称加密,数字证书,数字签名</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/JavaScript-WeakMap-ES6/">JavaScript,WeakMap,ES6</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/css-white-space-word-break-word-wrap-html/">css,white-space,word-break,word-wrap,html</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/immutable-js-immutable-JavaScript-持久化数据结构-结构共享-Vector-Trie-Clojure/">immutable.js,immutable,JavaScript,持久化数据结构,结构共享,Vector Trie,Clojure</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/immutable-js-immutable-JavaScript-持久化数据结构-结构共享-bitmap-transient-hash冲突-Vector-Trie-Clojure/">immutable.js,immutable,JavaScript,持久化数据结构,结构共享,bitmap,transient,hash冲突,Vector Trie,Clojure</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/尾递归-尾调用-trampoline-递归-迭代/">尾递归,尾调用,trampoline,递归,迭代</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/tags/HTTPS-SSL-TLS-加密-对称加密-非对称加密-数字证书-数字签名/" style="font-size: 10px;">HTTPS,SSL,TLS,加密,对称加密,非对称加密,数字证书,数字签名</a> <a href="/tags/JavaScript-WeakMap-ES6/" style="font-size: 10px;">JavaScript,WeakMap,ES6</a> <a href="/tags/css-white-space-word-break-word-wrap-html/" style="font-size: 10px;">css,white-space,word-break,word-wrap,html</a> <a href="/tags/immutable-js-immutable-JavaScript-持久化数据结构-结构共享-Vector-Trie-Clojure/" style="font-size: 10px;">immutable.js,immutable,JavaScript,持久化数据结构,结构共享,Vector Trie,Clojure</a> <a href="/tags/immutable-js-immutable-JavaScript-持久化数据结构-结构共享-bitmap-transient-hash冲突-Vector-Trie-Clojure/" style="font-size: 10px;">immutable.js,immutable,JavaScript,持久化数据结构,结构共享,bitmap,transient,hash冲突,Vector Trie,Clojure</a> <a href="/tags/尾递归-尾调用-trampoline-递归-迭代/" style="font-size: 10px;">尾递归,尾调用,trampoline,递归,迭代</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/03/">March 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/10/">October 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/09/">September 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/08/">August 2018</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2019/03/04/写了一个可以拦截ajax请求并修改返回结果的插件/">写了一个可以拦截ajax请求并修改返回结果的chrome插件</a>
          </li>
        
          <li>
            <a href="/2018/10/17/Javascript的尾递归及其优化/">Javascript的尾递归及其优化</a>
          </li>
        
          <li>
            <a href="/2018/09/19/深入探究immutable.js的实现机制（二）/">深入探究immutable.js的实现机制（二）</a>
          </li>
        
          <li>
            <a href="/2018/09/12/深入探究immutable.js的实现机制（一）/">深入探究immutable.js的实现机制（一）</a>
          </li>
        
          <li>
            <a href="/2018/09/04/彻底搞懂https的加密机制/">彻底搞懂HTTPS的加密机制</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2019 顾伊凡<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>



  </div>
</body>
</html>